0/1 Knapsack Approaches

Interactive algorithm analysis & benchmarking — generated by algoscope

Notes

Comparison of brute force, recursion, memoization, tabulation, and 1D DP.

Beginner Summary

knapsack_bruteforce

When the input size n doubles, the runtime grows by approximately 4.58×, which suggests performance closest to O(n log n).

insights
knapsack_recursive

When the input size n doubles, the runtime grows by approximately 2.67×, which suggests performance closer to O(n).

insights
knapsack_memo

When the input size n doubles, the runtime grows by approximately 1.58×, which suggests performance closer to O(n).

insights
knapsack_tab

When the input size n doubles, the runtime grows by approximately 1.48×, which suggests performance closer to O(log n).

insights
knapsack_1d

When the input size n doubles, the runtime grows by approximately 1.41×, which suggests performance closer to O(log n).

insights

Interview Summary

knapsack_bruteforce
Quick

knapsack_bruteforce has an estimated time complexity of O(n^2) and space complexity of O(1). For recursive implementations that halve the search space (e.g., binary search), space is O(log n) due to recursion depth; iterative versions are O(1) space.

knapsack_recursive
Quick

knapsack_recursive has an estimated time complexity of O(n) and space complexity of O(n). For recursive implementations that halve the search space (e.g., binary search), space is O(log n) due to recursion depth; iterative versions are O(1) space.

knapsack_memo
Quick

knapsack_memo has an estimated time complexity of O(n) and space complexity of O(n). For recursive implementations that halve the search space (e.g., binary search), space is O(log n) due to recursion depth; iterative versions are O(1) space.

knapsack_tab
Quick

knapsack_tab has an estimated time complexity of O(n^2) and space complexity of O(1). For recursive implementations that halve the search space (e.g., binary search), space is O(log n) due to recursion depth; iterative versions are O(1) space.

knapsack_1d
Quick

knapsack_1d has an estimated time complexity of O(n^2) and space complexity of O(1). For recursive implementations that halve the search space (e.g., binary search), space is O(log n) due to recursion depth; iterative versions are O(1) space.

Quick Stats

memory
6
Input sizes (n)
timer
6 measured sizes
Measured points

Use the tabs below to explore charts, memory, comparisons, and method details.

Manual Big-O Analysis

knapsack_bruteforce

Time: O(n^2) • Space: O(1)

Why: Nested loops detected; suggests quadratic time with constant extra space. These are heuristics; empirical results below provide a practical check.

knapsack_recursive

Time: O(n) • Space: O(n)

Why: Detected recursion without loops and no clear halving pattern. This commonly implies linear recursion depth and O(n) time/space. These are heuristics; empirical results below provide a practical check.

knapsack_memo

Time: O(n) • Space: O(n)

Why: Detected recursion without loops and no clear halving pattern. This commonly implies linear recursion depth and O(n) time/space. These are heuristics; empirical results below provide a practical check.

knapsack_tab

Time: O(n^2) • Space: O(1)

Why: Nested loops detected; suggests quadratic time with constant extra space. These are heuristics; empirical results below provide a practical check.

knapsack_1d

Time: O(n^2) • Space: O(1)

Why: Nested loops detected; suggests quadratic time with constant extra space. These are heuristics; empirical results below provide a practical check.

Beginner & Interview Summaries

knapsack_bruteforce

When the input size n doubles, the runtime grows by approximately 4.58×, which suggests performance closest to O(n log n).

Interview: knapsack_bruteforce has an estimated time complexity of O(n^2) and space complexity of O(1). For recursive implementations that halve the search space (e.g., binary search), space is O(log n) due to recursion depth; iterative versions are O(1) space.

knapsack_recursive

When the input size n doubles, the runtime grows by approximately 2.67×, which suggests performance closer to O(n).

Interview: knapsack_recursive has an estimated time complexity of O(n) and space complexity of O(n). For recursive implementations that halve the search space (e.g., binary search), space is O(log n) due to recursion depth; iterative versions are O(1) space.

knapsack_memo

When the input size n doubles, the runtime grows by approximately 1.58×, which suggests performance closer to O(n).

Interview: knapsack_memo has an estimated time complexity of O(n) and space complexity of O(n). For recursive implementations that halve the search space (e.g., binary search), space is O(log n) due to recursion depth; iterative versions are O(1) space.

knapsack_tab

When the input size n doubles, the runtime grows by approximately 1.48×, which suggests performance closer to O(log n).

Interview: knapsack_tab has an estimated time complexity of O(n^2) and space complexity of O(1). For recursive implementations that halve the search space (e.g., binary search), space is O(log n) due to recursion depth; iterative versions are O(1) space.

knapsack_1d

When the input size n doubles, the runtime grows by approximately 1.41×, which suggests performance closer to O(log n).

Interview: knapsack_1d has an estimated time complexity of O(n^2) and space complexity of O(1). For recursive implementations that halve the search space (e.g., binary search), space is O(log n) due to recursion depth; iterative versions are O(1) space.

Runtime Chart

Runtime Table (mean ± 95% CI)

n knapsack_bruteforce knapsack_recursive knapsack_memo knapsack_tab knapsack_1d
5 19.40 µs ± 1.50 µs 9.29 µs ± 2.38 µs 12.74 µs ± 3.63 µs 11.64 µs ± 633.67 ns 8.11 µs ± 1.55 µs
7 85.90 µs ± 9.16 µs 26.26 µs ± 13.91 µs 23.78 µs ± 14.51 µs 19.54 µs ± 1.19 µs 12.11 µs ± 1.04 µs
9 393.11 µs ± 33.24 µs 91.40 µs ± 14.36 µs 37.25 µs ± 8.18 µs 31.39 µs ± 2.46 µs 17.40 µs ± 2.73 µs
11 1.84 ms ± 51.26 µs 171.71 µs ± 143.11 µs 52.18 µs ± 30.23 µs 46.97 µs ± 3.03 µs 28.40 µs ± 13.50 µs
13 8.69 ms ± 312.99 µs 410.46 µs ± 457.26 µs 92.50 µs ± 53.74 µs 66.49 µs ± 11.64 µs 32.88 µs ± 1.69 µs
15 38.88 ms ± 1.91 ms 1.14 ms ± 2.17 ms 119.83 µs ± 49.96 µs 78.57 µs ± 1.74 µs 43.37 µs ± 6.12 µs

Peak Memory Chart

Memory Table (mean ± 95% CI)

n knapsack_bruteforce knapsack_recursive knapsack_memo knapsack_tab knapsack_1d
5 208.00 B ± 0.00 B 130.67 B ± 80.32 B 1.19 KB ± 1.18 KB 1.02 KB ± 160.65 B 408.00 B ± 0.00 B
7 225.33 B ± 50.99 B 206.00 B ± 284.00 B 2.90 KB ± 2.54 KB 1.41 KB ± 0.00 B 486.67 B ± 106.26 B
9 257.33 B ± 40.16 B 130.67 B ± 40.16 B 5.89 KB ± 5.47 KB 2.12 KB ± 281.13 B 658.67 B ± 503.22 B
11 304.00 B ± 0.00 B 158.67 B ± 40.16 B 6.85 KB ± 250.81 B 3.33 KB ± 944.43 B 774.67 B ± 328.73 B
13 304.00 B ± 0.00 B 233.33 B ± 263.36 B 11.43 KB ± 9.96 KB 4.28 KB ± 1.00 KB 1.02 KB ± 240.97 B
15 304.00 B ± 0.00 B 289.33 B ± 200.81 B 13.77 KB ± 463.16 B 6.02 KB ± 3.12 KB 922.67 B ± 281.13 B

Comparison Summary

Best/worst runtime at each n (lower is better). Mean ranks summarize performance across all n.

n Best Runtime Worst Runtime Mean Ranks
5 knapsack_1d knapsack_bruteforce knapsack_bruteforce: 5.00 knapsack_recursive: 3.67 knapsack_memo: 3.17 knapsack_tab: 2.17 knapsack_1d: 1.00
7 knapsack_1d knapsack_bruteforce knapsack_bruteforce: 5.00 knapsack_recursive: 3.67 knapsack_memo: 3.17 knapsack_tab: 2.17 knapsack_1d: 1.00
9 knapsack_1d knapsack_bruteforce knapsack_bruteforce: 5.00 knapsack_recursive: 3.67 knapsack_memo: 3.17 knapsack_tab: 2.17 knapsack_1d: 1.00
11 knapsack_1d knapsack_bruteforce knapsack_bruteforce: 5.00 knapsack_recursive: 3.67 knapsack_memo: 3.17 knapsack_tab: 2.17 knapsack_1d: 1.00
13 knapsack_1d knapsack_bruteforce knapsack_bruteforce: 5.00 knapsack_recursive: 3.67 knapsack_memo: 3.17 knapsack_tab: 2.17 knapsack_1d: 1.00
15 knapsack_1d knapsack_bruteforce knapsack_bruteforce: 5.00 knapsack_recursive: 3.67 knapsack_memo: 3.17 knapsack_tab: 2.17 knapsack_1d: 1.00

Mean Runtime Comparison (bar)

Bar chart placeholder: you can render an additional Plotly bar chart here comparing means per function.

Methods & Notes

  • Runtime measured with time.perf_counter(); each (function, n) pair ran 3 times after 2 warmup iterations. GC was enabled and collected before runs.
  • Memory peak measured with tracemalloc backend (tracemalloc by default).
  • Confidence Intervals: T at 95% confidence. T-intervals use standard t critical values; bootstrap uses 2,000 resamples with a fixed seed.
  • Reference curves (O(1), O(log n), O(n), O(n log n), plus any custom) were normalized at the largest n to match the average observed runtime scale.